/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/24-game
   @Language: C++
   @Datetime: 19-04-18 10:45
   */


// Method 1, using combination, bfs, Time 101ms
class Solution {
	void combine(const vector<double> &nums, const int k, int begin, 
			vector<double> &tmp, vector<vector<double> > &com){
		if(tmp.size()==k){
			com.push_back(tmp);
			return;
		}
		for(int i=begin; i<nums.size() && tmp.size()<k; ++i){
			tmp.push_back(nums[i]);
			combine(nums,k,i+1,tmp,com);
			tmp.pop_back();
		}
	}

public:
	/**
	 * @param nums: 4 cards
	 * @return: whether they could get the value of 24
	 */
	bool compute24(vector<double> &nums) {
		// write your code here
		const int target=24;
		queue<pair<vector<double>,vector<double> > > que;
		for(que.push({nums,{}}); que.size(); que.pop()){
			auto &sel=que.front().first;
			auto &last=que.front().second;
			vector<double> v;
			vector<vector<double> > com;
			if(sel.size()==1){
				if(abs(sel[0]-target)<1e-6) return true;
				else continue;
			}
			if(sel.size()==2){
				last.push_back(0);
				last.back()=sel[0]+sel[1];
				que.push({last,v});
				last.back()=sel[0]*sel[1];
				que.push({last,v});
				last.back()=sel[0]-sel[1];
				que.push({last,v});
				last.back()=sel[1]-sel[0];
				que.push({last,v});
				if(abs(sel[1])>1e-6){
					last.back()=sel[0]/sel[1];
					que.push({last,v});
				}
				if(abs(sel[0])>1e-6){
					last.back()=sel[1]/sel[0];
					que.push({last,v});
				}
				continue;
			}
			combine(sel,2,0,v,com);
			for(const auto &c:com){
				sel.erase(find(sel.begin(),sel.end(),c[0]));
				sel.erase(find(sel.begin(),sel.end(),c[1]));
				que.push({c,sel});
				sel.push_back(c[0]);
				sel.push_back(c[1]);
			}
		}
		return false;
	}
};


// Method 2, Time 50ms
class Solution {
	void core(vector<double> &nums, bool &found){
		if(nums.size()==1){
			found |= abs(nums[0]-24)<1e-6;
			return;
		}
		for(int i=0; i<nums.size(); ++i){
			for(int j=i+1; j<nums.size(); ++j){
				const double a=nums[i], b=nums[j];
				vector<double> v={a+b,a*b,a-b,b-a};
				if(abs(a)>1e-6) v.push_back(b/a);
				if(abs(b)>1e-6) v.push_back(a/b);
				nums.erase(nums.begin()+j);
				nums.erase(nums.begin()+i);
				for(const double &t:v){
					nums.push_back(t);
					core(nums,found);
					nums.pop_back();
				}
				nums.insert(nums.begin()+i,a);
				nums.insert(nums.begin()+j,b);
			}
		}
	}

public:
	/**
	 * @param nums: 4 cards
	 * @return: whether they could get the value of 24
	 */
	bool compute24(vector<double> &nums) {
		// write your code here
		bool found=false;
		core(nums,found);
		return found;
	}
};

// Method 3, hard code, time 50ms
class Solution {
	bool judge(double a, double b){
		return abs(a+b-24)<1e-6||abs(a*b-24)<1e-6||abs(a-b-24)<1e-6||
			(abs(b)>1e-6&&abs(a/b-24)<1e-6);
	}
	bool judge(double a, double b, double c){
		return judge(a+b,c)||judge(a*b,c)||judge(a-b,c)||(abs(b)>1e-6&&judge(a/b,c))||
			judge(a,b+c)||judge(a,b*c)||judge(a,b-c)||(abs(c)>1e-6&&judge(a,b/c));
	}
	bool judge(double a, double b, double c, double d){
		return judge(a+b,c,d)||judge(a*b,c,d)||judge(a-b,c,d)||(abs(b)>1e-6&&judge(a/b,c,d))||
			judge(a,b+c,d)||judge(a,b*c,d)||judge(a,b-c,d)||(abs(c)>1e-6&&judge(a,b/c,d))||
			judge(a,b,c+d)||judge(a,b,c*d)||judge(a,b,c-d)||(abs(d)>1e-6&&judge(a,b,c/d));
	}

public:
	/**
	 * @param nums: 4 cards
	 * @return: whether they could get the value of 24
	 */
	bool compute24(vector<double> &nums) {
		// write your code here
		sort(nums.begin(),nums.end());
		do{
			if(judge(nums[0],nums[1],nums[2],nums[3])) return true;
		}while(next_permutation(nums.begin(),nums.end()));
		return false;
	}
};
